package 按之字形打印二叉树;

import java.util.ArrayList;
import java.util.Stack;

//题目描述
//请实现一个函数按照之字形打印二叉树，
// 即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
public class Solution
{
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot)
    {
        //判断输入
        ArrayList<ArrayList<Integer>> integers = new ArrayList<>();
        if (pRoot == null)
            return integers;

        Stack<TreeNode> stack1 = new Stack<>();//偶数栈
        Stack<TreeNode> stack2 = new Stack<>();//技术栈

        //把根节点放进栈
        stack1.push(pRoot);
        //判断同一层节点，每一层出队开始前，计算队列的长度size，然后循环size次进行出队操作
        int row = 0;
        //不能使用一个栈，会导致上一行的没弹出完毕，就开始弹出别的下一行的了
        //使用两个栈，一个奇数栈，一个偶数栈
        while (!stack1.isEmpty()||!stack2.isEmpty())
        {
            ArrayList<Integer> list1 = new ArrayList<>();
            TreeNode temp=null;
            while (!stack1.isEmpty())
            {
                temp = stack1.pop();
                int p = temp.val;
                list1.add(p);

                if (temp.left != null)
                    stack2.push(temp.left);
                if (temp.right != null)
                    stack2.push(temp.right);

            }
            if (list1.size()!=0)
                integers.add(list1);
            ArrayList<Integer> list2 = new ArrayList<>();
            while (!stack2.isEmpty())
            {
                temp = stack2.pop();
                int p = temp.val;
                list2.add(p);
                if (temp.right != null)
                    stack1.push(temp.right);
                if (temp.left != null)
                    stack1.push(temp.left);

            }
            if (list2.size()!=0)
                integers.add(list2);
        }

        return integers;
    }

    public static void main(String[] args)
    {
        TreeNode node1 = new TreeNode(8);
        TreeNode node2 = new TreeNode(6);
        TreeNode node3 = new TreeNode(10);
        TreeNode node4 = new TreeNode(5);
        TreeNode node5 = new TreeNode(7);
        TreeNode node6 = new TreeNode(9);
        TreeNode node7 = new TreeNode(11);
        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;
        node3.right=node7;
        Solution solution = new Solution();
        System.out.println(solution.Print(node1));
    }
}
